package Permutations_II


import "sort"
/*
与上一个全排列不同的是，这个全排列切片中有相同的数，如果还是按照上一个进行计算，可能导致不同位置相同的数排列后在相同的位置。
在上一个基础上，添加一个去重的判断，还要判断是否在同一递归层面上
 */
func main() {
	permuteUnique([]int{1, 1, 2})
}

var destination [][]int

var result [][]int

func permuteUnique(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	sort.Ints(nums)
	backtrace(nums, []int{}, make([]bool, 8))
	return result
}

func backtrace(nums []int, pathnum []int, used []bool) {
	if len(nums) == len(pathnum) {
		tmp := make([]int, len(nums))
		copy(tmp, pathnum)
		result = append(result, tmp)
		return
	}
	for i := 0; i < len(nums); i++ {
		//如果i大于等于1，并且和前面的数值相等，并且属于同一层的，跳过循环
		if i >= 1 && nums[i-1] == nums[i] && !used[i-1] {
			continue
		}
		if !used[i] {
			used[i] = true
			pathnum = append(pathnum, nums[i])
			backtrace(nums, pathnum, used)
			pathnum = pathnum[:len(pathnum)-1]
			used[i] = false
		}
	}
}
